冒泡排序

• 重复走过要排序的元素列
• 依次比较两个相邻的元素
• 如果顺序错误，就交换他们的位置

实现过程

def bubble_sort(alist):
    """冒泡排序"""
    # 数列的长度
    n = len(alist)

    # 控制比较轮数
    for j in range(0, n - 1):
        # 计数
        count = 0
        # 控制每一轮的比较次数
        for i in range(0, n - 1 - j):
            # 比较相邻的两个数字，不符合要求交换位置
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i + 1], alist[i]
                count += 1

        # 如果遍历一变发现没有数字交换，退出循环，证明数列是有序的
        if count == 0:
            break

if __name__ == '__main__':
    alist = [5, 3, 4, 7, 2]
    bubble_sort(alist)
    print(alist)

Java版实现

/*
冒泡排序 {3, 5, 2, 1, 4}

1. 相邻的元素两两比较，大的放右边，小的放左边，找到最大值
2. 第一次循环结束，最大值已经找到，在数组的最右边 // {3, 2, 1, 4, 5}
3. 下一次只要在剩余的元素找最大值就可以了
4. 因为已经确定了5是最大值，所以4跟5无需再进行比较了// {2, 1, 3, 4, 5}
5. 因为已经确定了5是最大值，4是次大值。所以3无须再跟4和5再进行比较了
6. 同理3,4,5的位置已经确定了，2也无须这三个值进行比较了// {1, 2, 3, 4, 5}
7. 最后只剩下一个值1了，肯定就放在最后一个格子中了

- 分析：
    - 如果有n个数据进行排序，总共需要比较n-1次
    - 每一次比较完毕，下一次的比较就会少一个数据参与
- */
private static void binarySort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // 每个元素和右边的元素比较，大的放到右边
                if (arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

冒泡排序的稳定性

时间复杂度为$O(n^2)$，是一个稳定的算法。